package _剑指offer._公司题目._华为;

import org.junit.Test;

import java.util.*;


/**
 * 思路整理：
 *      按行读取输入，并 split 分别存到 List<String[]> ；
 *      中间使用 dfs 算法 ，考虑站数最多的时候效益最多，
 *          记录当前站数，当超过5站return，
 *          for 循环里遍历每一个，添加，计算站数，末尾站作为当前站，删除；
 *      最终的答案放到 list<String> 最后排序打印
 *
 */
public class _03_ {

    @Test
    public void main() {

    }

    static List<String> res = new ArrayList<>();
    static int total_states = 0;

    public static void main(String[] args) {
//        Scanner sc = new Scanner(System.in);
        List<String[]> list = new ArrayList<>();
//        int k = 0;
//        while(k++ < 15 && sc.hasNextLine()){
//            String str = sc.nextLine();
//            String[] strs = str.split(",");
//            if(strs.length != 3)break;
//            list.add(strs);
//        }

        //                     0    1    2
        list.add(new String[]{"a", "1", "5"});
        list.add(new String[]{"b", "3", "5"});
        list.add(new String[]{"c", "1", "3"});

        dfs(list, new ArrayList<Integer>(), 0, 0);

        Collections.sort(res);
        for(String str : res){
            System.out.print(str + " ");
        }
    }

    private static void dfs(List<String[]> list, ArrayList<Integer> people, int states, int idx) {
        if(res.size() == 5) return;
        if(states>total_states || (states==total_states&&people.size()>res.size())){
            total_states = states;
            res = new ArrayList<>();
            for(int i :people){
                res.add(list.get(i)[0]);
            }
        }
        for(int i=0; i<list.size(); i++){
            if(Integer.parseInt(list.get(i)[1])==idx || idx==0){
                people.add(i);
                dfs(list, people, states+Integer.parseInt(list.get(i)[2])-Integer.parseInt(list.get(i)[1]), Integer.parseInt(list.get(i)[2]));
                people.remove(people.size()-1);
            }
        }
    }


}
